#include<iostream>
#include "../module/graph.h"
#include<map>
#include<algorithm>
using namespace std;

class Djkstra
{
private:
    Graph G;
    int node_num;
    int edge_num;
    int start_node;
    Node* headNode;
public:
    Djkstra() {
        cin >> node_num >> edge_num >> start_node;
        for(int i=0; i<edge_num; i++) {
            int from,to,weight;
            //起点 终点 距离 有向边
            cin >> from >> to >> weight;
            //创建起点 终点
            this->G.addNode(from);
            this->G.addNode(to);
            //创建连线
            this->G.addEdge(from,to,weight);
        }
        headNode = this->G.nodes.find(start_node)->second;
        this->G.showGraph();
    }

    Node* getMinDistanceAndUnselectedNode(const unordered_map<Node*,int>& distanceMap,const set<Node*>& selectNodes) {
        int minDistance = 0x7fff;
        Node* retMinDistanceNode = nullptr;
        for(auto it=distanceMap.begin(); it!=distanceMap.end(); it++) {
            //还没有被寻到 且距离小于当前minDistance
            if(selectNodes.find((*it).first) == selectNodes.end() && minDistance > (*it).second) {
                retMinDistanceNode = (*it).first;
            }
        }
        return retMinDistanceNode;
    } 

    void showMap(const unordered_map<Node*,int>& distanceMap) {
        cout << "Map:" << endl;
        for(auto it=distanceMap.begin(); it!=distanceMap.end(); it++) {
            cout << "\tnode:" << (*it).first->value << " dis:" << (*it).second << endl;
        }
    }

    void findPath() {
        unordered_map<Node*,int> distanceMap; //从start出发的点,到Node的最小距离
        distanceMap.insert(pair<Node*,int>(headNode,0));
        set<Node*> selectNodes; //已经被选择过的节点
        Node* minNode = this->getMinDistanceAndUnselectedNode(distanceMap,selectNodes);
        while(minNode != nullptr) {
            //获取当前节点距起点距离
            int distance = distanceMap.find(minNode)->second;
            cout << "minNode:" << minNode->value << " distance:" << distance << endl;
            //遍历minNode所有所属边,更新distanceMap
            auto edges = distanceMap.find(minNode)->first->edges;
            for(auto eit=edges.begin(); eit!=edges.end(); eit++) {
                Node* to_node = (*eit)->to;
                //如果distanceMap里面不含有to_node(表示无穷远) 将to_node添加进map里面
                if(distanceMap.find(to_node) == distanceMap.end()) {
                    distanceMap.insert(pair<Node*,int>(to_node,(*eit)->weight));
                } else {
                    //更新当前节点附属距离
                    cout << "\t\tupdate" << endl;
                    int dist1 = distanceMap.find(to_node)->second;
                    int dist2 = distance + (*eit)->weight;
                    cout << "\t\tdist1:" << dist1 << " dist2:" << dist2 << endl;
                    int mindist = min(dist1,dist2);
                    cout << "\t\tmindist:" << mindist << endl;
                    // distanceMap.insert(pair<Node*,int>(to_node,mindist));
                    distanceMap.find(to_node)->second = mindist;
                }
            }
            this->showMap(distanceMap);
            selectNodes.insert(minNode);
            minNode = this->getMinDistanceAndUnselectedNode(distanceMap,selectNodes);
        }
        cout << "startNode:" << this->headNode->value << endl;
        this->showMap(distanceMap);
    }
};

int main() {
    Djkstra D;
    D.findPath();
    return 0;
}